A wiring design apparatus which automatically or semi-automatically designs a wiring of a printed circuit substrate or a wiring between bonding pads of a semiconductor chip and pins (terminals) of a semiconductor package which is used in a electronic equipment is disclosed in PUPA 5-143689. An improvement of wiring route and design speed has been disclosed, however, it is not determined until the wiring design has been completed whether or not wiring of a printed circuit and the like is 100% possible (whether or not a wiring solution exists) in the prior art wiring design apparatus.
In designing wiring in a specific area such as a wiring of a semiconductor package, an illegal wiring in which the wire density among the pins is unnecessarily dense and the route detours excessively, or turns round the periphery of pins has to be detected and corrected even if there is a wiring solution.
However, prior to this invention it was not possible to detect such illegal wiring until the wiring design had been completed in the prior art wiring design apparatus.
When the prior art wiring design apparatus was used, additional work for correcting information of the subject of wiring (design information) included disposition of parts on a printed circuit substrate or disposition of bonding pads of a semiconductor chip and pins of a semiconductor package, work on wiring design and work of detecting and correcting an illegal wiring have to be repeated again and again until a wiring solution is obtained and all the wires follow an optimum route.
Such repetition of work took a very long time and it is a heavy burden on the designer.
On the other hand, "Algorithm C++" by Robert Sedwick published by Kindai-Kagaku Co., pages 461-; (original publication "Algorithm in C++", 1990, Addison Wesley Co.., Inc., MA, USA) discloses Volonoi polygon method and Delaunay triangulation method (they are essentially the same though differently named) as a method of solving a problem relating to a distance between an arbitrary point on a plane and multiple points (mother points) given on the same plane. No wiring determination apparatus has ever existed so far which uses Delaunay triangulation method in wiring design to quickly determine presence or absence of wiring solution for detecting and correcting an illegal wiring.